import java.util.*;

/**
 * 987. 二叉树的垂序遍历
 * https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree/
 */
public class Solutions_987 {
    public static void main(String[] args) {
        String str = "[3 9 20 # # 15 7]";  // output: {{9}, {3, 15}, {20}, {7}}
//        String str = "[1 2 3 4 5 6 7]";  // output: {{4}, {2}, {1, 5, 6}, {3}, {7}}

        TreeNode root = MyTreeNodeUtils.deserialize(str);
        List<List<Integer>> result = verticalTraversal(root);
        System.out.println(result);
    }

    public static List<List<Integer>> verticalTraversal(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<Node_987> list = new ArrayList<>();
        // 遍历树，将全部的节点，创建为 Node_987 对象，并存储到 list 中
        dfs(root, 0, 0, list);
        // 对 list 进行排序，Node_987 类中已重写 compareTo 方法
        Collections.sort(list);

        List<List<Integer>> res = new ArrayList<>();
        int prevX = list.get(0).x;
        res.add(new ArrayList<>());

        for (int i = 0; i < list.size(); i++) {
            Node_987 node = list.get(i);
            if (node.x != prevX) {
                // x 轴不同时，说明是新的一列
                prevX = node.x;
                res.add(new ArrayList<>());
            }
            // node.val 添加到 res 里最后一条记录中
            res.get(res.size() - 1).add(node.val);
        }
        return res;
    }

    public static void dfs(TreeNode root, int x, int y, List<Node_987> list) {
        if (root == null) {
            return;
        }
        Node_987 node = new Node_987(x, y, root.val);
        list.add(node);
        dfs(root.left, x - 1, y - 1, list);
        dfs(root.right, x + 1, y - 1, list);
    }
}

class Node_987 implements Comparable<Node_987> {
    int x;
    int y;
    int val;

    Node_987(int x, int y, int val) {
        this.x = x;
        this.y = y;
        this.val = val;
    }

    @Override
    public int compareTo(Node_987 o1) {
        // 排序规则：根据 X 轴升序排列
        // 若 X 轴相同，再根据 Y 轴降序排列
        // 若 Y 轴相同，则根据 val 值升序排列
        if (this.x == o1.x) {
            if (this.y == o1.y) {
                // val 值升序排列
//                return this.val - o1.val;
                // 使用 Integer.compare，防止数值溢出
                return Integer.compare(this.val, o1.val);
            } else {
                // Y 轴降序排列
//                return o1.y - this.y;
                return Integer.compare(o1.y, this.y);
            }
        } else {
            // X 轴升序排列
//            return this.x - o1.x;
            return Integer.compare(this.x, o1.x);
        }
    }
}
